{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\na = 10  # 把10的地址交给a\\nb = 10\\na,b=b,a # 交换a,b\\n\\npython中变量名保存的是对象的地址，只关心地址，不关心地址所指向的数据类型\\na = 10\\na = def func()\\na = class Node()\\n\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "    链表实际上就是把分离式顺序表中一个元素的数据和下一个元素的内存地址放在一块内存中。\n",
    "    顺序表和链表统称为线性表。\n",
    "    与顺序表的优势是：不需要连续内存，但是额外内存开销变大，不过查找和插入的效率变低。\n",
    "\n",
    "    原则就是： 先打断谁\n",
    "'''\n",
    "\n",
    "# 变量的本质\n",
    "'''\n",
    "a = 10  # 把10的地址交给a\n",
    "b = 10\n",
    "a,b=b,a # 交换a,b\n",
    "\n",
    "python中变量名保存的是对象的地址，只关心地址，不关心地址所指向的数据类型\n",
    "a = 10\n",
    "a = def func()\n",
    "a = class Node()\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0\n",
      "False\n",
      "1\n",
      "\n",
      "\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "100\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n",
      "\n",
      "\n",
      "True\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "# 单向链表\n",
    "\n",
    "class Node(object):\n",
    "    # 定义节点\n",
    "    def __init__(self, elem):\n",
    "        self.elem = elem\n",
    "        self.next = None\n",
    "    \n",
    "\n",
    "class SingleLinkList(object):\n",
    "    \"\"\"\n",
    "        实现单向链表\n",
    "    \"\"\"\n",
    "    def __init__(self, node=None):\n",
    "        # 私有变量是双下划线\n",
    "        self.head = node\n",
    "        \n",
    "    # 判空\n",
    "    def is_empty(self):\n",
    "        return self.head is None\n",
    "    \n",
    "    # 长度\n",
    "    def length(self):\n",
    "        cnt=0\n",
    "        cur = self.head\n",
    "        while cur:\n",
    "            cnt+=1\n",
    "            cur = cur.next\n",
    "        return cnt\n",
    "    \n",
    "    # 遍历\n",
    "    def travel(self):\n",
    "        cur =self.head\n",
    "        while cur:\n",
    "            print(cur.elem)\n",
    "            cur = cur.next\n",
    "        \n",
    "    \n",
    "    # 头部添加 O(1)\n",
    "    def add(self, item):\n",
    "        node = Node(item)\n",
    "        node.next = self.head\n",
    "        self.head = node\n",
    "    \n",
    "    # 尾部添加 O(n)\n",
    "    def append(self, item):\n",
    "        node = Node(item)\n",
    "        if self.is_empty():\n",
    "            self.head = node\n",
    "        else:\n",
    "            cur = self.head\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "            cur.next = node\n",
    "    \n",
    "    # 指定位置添加 O(n)\n",
    "    def insert(self, pos, item):\n",
    "        node = Node(item)\n",
    "        pre = self.head\n",
    "        if pos <= 0:\n",
    "            self.add(item)\n",
    "        elif pos > (self.length() -1):\n",
    "            self.append(item)\n",
    "        else:\n",
    "            cnt = 0\n",
    "            while cnt < pos-1:\n",
    "                pre = pre.next\n",
    "                cnt+=1\n",
    "            node.next=pre.next\n",
    "            pre.next = node\n",
    "\n",
    "    # 删除指定元素 O(n)\n",
    "    # 只删除找到的第一个元素\n",
    "    # 用双指针真爽\n",
    "    def remove(self, item):\n",
    "        cur = self.head\n",
    "        pre = None\n",
    "        while cur:\n",
    "            if cur.elem is item:\n",
    "                if cur is self.head:\n",
    "                    self.head = cur.next\n",
    "                else:\n",
    "                    pre.next=cur.next\n",
    "                return\n",
    "            else:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "    \n",
    "    # 搜索指定元素 O(n)\n",
    "    def search(self, item):\n",
    "        cur = self.head\n",
    "        while cur:\n",
    "            if cur.elem is item:\n",
    "                return True\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        return False\n",
    "    \n",
    "    \n",
    "if __name__ == \"__main__\":\n",
    "    sll = SingleLinkList()\n",
    "    \n",
    "    print(sll.is_empty()) # True\n",
    "    print(sll.length())   # 0\n",
    "    \n",
    "    sll.add(1) \n",
    "    print(sll.is_empty()) # False\n",
    "    print(sll.length())   # 1\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    sll.append(2)\n",
    "    sll.append(3)\n",
    "    sll.append(4)\n",
    "    sll.append(5)\n",
    "    sll.append(6)\n",
    "    sll.travel()  # 1 2 3 4 5 6\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    sll.add(0)\n",
    "    sll.travel() # 0 1 2 3 4 5 6\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    sll.insert(7,8)\n",
    "    sll.travel()  # 0 1 2 3 4 5 6 8\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    sll.insert(2,100)\n",
    "    sll.travel()  # 0 1 2 100 3 4 5 6 8\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    print(sll.search(8))\n",
    "    print(\"\\n\") # True\n",
    "    \n",
    "    sll.remove(100)\n",
    "    sll.travel() # # 0 1 2 3 4 5 6 8\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0\n",
      "\n",
      "\n",
      "False\n",
      "1\n",
      "\n",
      "\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n",
      "\n",
      "\n",
      "0\n",
      "100\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n",
      "\n",
      "\n",
      "True\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "双向链表\n",
    "'''\n",
    "class Node(object):\n",
    "    def __init__(self, item):\n",
    "        self.elem = item\n",
    "        self.prev = None\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class DoubleLinkList(SingleLinkList):\n",
    "    \"\"\"\n",
    "        is_empty()\n",
    "        lengh()\n",
    "        travel() 方法都是能复用单链表的\n",
    "    \"\"\"\n",
    "    def __init__(self, node=None):\n",
    "        SingleLinkList.__init__(self)\n",
    "\n",
    "    # 头部添加 O(1)\n",
    "    def add(self, item):\n",
    "        node = Node(item)\n",
    "        \n",
    "        if self.head is None:\n",
    "            self.head = node\n",
    "        else:\n",
    "            node.next = self.head\n",
    "            self.head = node\n",
    "            node.next.prev = node\n",
    "    \n",
    "    # 尾部添加 O(n)\n",
    "    def append(self, item):\n",
    "        node = Node(item)\n",
    "        if self.is_empty():\n",
    "            self.head = node\n",
    "        else:\n",
    "            cur = self.head\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "            cur.next = node\n",
    "            node.prev = cur\n",
    "    \n",
    "    # 指定位置的下一个位置添加 O(n)\n",
    "    def insert(self, pos, item):\n",
    "        node = Node(item)\n",
    "        cur = self.head\n",
    "        if pos <= 0:\n",
    "            self.add(item)\n",
    "        elif pos > (self.length() -1):\n",
    "            self.append(item)\n",
    "        else:\n",
    "            cnt = 0\n",
    "            while cnt < pos-1:\n",
    "                cur = cur.next\n",
    "                cnt+=1\n",
    "            # 先不打断原来的\n",
    "            node.next=cur\n",
    "            node.prev = cur.prev\n",
    "            \n",
    "            # 再打断原来的\n",
    "            cur.prev.next = node\n",
    "            cur.prev = node\n",
    "\n",
    "    # 删除指定元素 O(n)\n",
    "    # 只删除找到的第一个元素\n",
    "    def remove(self, item):\n",
    "        cur = self.head\n",
    "        while cur:\n",
    "            if cur.elem is item:\n",
    "                if cur is self.head:\n",
    "                    # 只有一个元素，并且和目标元素相同\n",
    "                    self.head = cur.next\n",
    "                else:\n",
    "                    cur.prev.next=cur.next\n",
    "                    if cur.next:\n",
    "                        # cur是最后一个节点\n",
    "                        cur.next.prev = cur.prev\n",
    "                break\n",
    "            else:\n",
    "                cur = cur.next\n",
    "\n",
    "\n",
    "\n",
    "if __name__==\"__main__\":\n",
    "    dll = DoubleLinkList()\n",
    "    \n",
    "    print(dll.is_empty())\n",
    "    print(dll.length())\n",
    "    print(\"\\n\")\n",
    "\n",
    "    dll.add(1) \n",
    "    print(dll.is_empty()) # False\n",
    "    print(dll.length())   # 1\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    dll.append(2)\n",
    "    dll.append(3)\n",
    "    dll.append(4)\n",
    "    dll.append(5)\n",
    "    dll.append(6)\n",
    "    dll.travel()  # 1 2 3 4 5 6\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    dll.add(0)\n",
    "    dll.travel() # 0 1 2 3 4 5 6\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    dll.insert(7,8)\n",
    "    dll.travel()  # 0 1 2 3 4 5 6 8\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    dll.insert(2,100)\n",
    "    dll.travel()  # 0 1 2 100 3 4 5 6 8\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    print(dll.search(8))\n",
    "    print(\"\\n\") # True\n",
    "    \n",
    "    dll.remove(100)\n",
    "    dll.travel() # # 0 1 2 3 4 5 6 8\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "0\n",
      "False\n",
      "1\n",
      "\n",
      "\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "100\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n",
      "\n",
      "\n",
      "True\n",
      "\n",
      "\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n",
      "\n",
      "\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "8\n",
      "\n",
      "\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "单向循环链表：\n",
    "    与单向循环链表的唯一区别是，尾部元素的next指向head\n",
    "'''\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, item):\n",
    "        self.elem = item\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class SingleLinkList(object):\n",
    "    \"\"\"\n",
    "        单向循环链表\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, node=None):\n",
    "        self.head = node\n",
    "        if node:\n",
    "            node.next = node\n",
    "    # 判空\n",
    "    def is_empty(self):\n",
    "        return self.head is None\n",
    "    \n",
    "    # 长度\n",
    "    def length(self):\n",
    "        if self.is_empty():\n",
    "            return 0\n",
    "        cnt=1\n",
    "        cur = self.head\n",
    "        while cur.next is not self.head:\n",
    "            cnt+=1\n",
    "            cur = cur.next\n",
    "        return cnt\n",
    "    \n",
    "    # 遍历\n",
    "    def travel(self):\n",
    "        cur =self.head\n",
    "        while cur.next is not self.head:\n",
    "            print(cur.elem)\n",
    "            cur = cur.next\n",
    "        # 用next去遍历时，尾部节点要单独处理\n",
    "        print(cur.elem)\n",
    "        \n",
    "    # 头部添加 O(1)\n",
    "    def add(self, item):\n",
    "        node = Node(item)\n",
    "        if self.is_empty():\n",
    "            self.head = node\n",
    "            node.next = node\n",
    "        else:\n",
    "            cur = self.head\n",
    "            while cur.next is not self.head:\n",
    "                cur = cur.next\n",
    "            cur.next = node\n",
    "            node.next = self.head\n",
    "            self.head = node\n",
    "    \n",
    "    # 尾部添加 O(n)\n",
    "    def append(self, item):\n",
    "        node = Node(item)\n",
    "        if self.is_empty():\n",
    "            self.head = node\n",
    "            node.next = node\n",
    "        else:\n",
    "            cur = self.head\n",
    "            while cur.next is not self.head:\n",
    "                cur = cur.next\n",
    "            cur.next = node\n",
    "            node.next = self.head\n",
    "    \n",
    "# 指定位置添加 O(n)\n",
    "    def insert(self, pos, item):\n",
    "        node = Node(item)\n",
    "        pre = self.head\n",
    "        if pos <= 0:\n",
    "            self.add(item)\n",
    "        elif pos > (self.length() -1):\n",
    "            self.append(item)\n",
    "        else:\n",
    "            cnt = 0\n",
    "            while cnt < pos-1:\n",
    "                # 用pos -1 来控制前一个node\n",
    "                pre = pre.next\n",
    "                cnt+=1\n",
    "            node.next=pre.next\n",
    "            pre.next = node\n",
    "\n",
    "    # 删除指定元素 O(n)\n",
    "    # 只删除找到的第一个元素\n",
    "    # 用双指针真爽\n",
    "    def remove(self, item):\n",
    "        if self.is_empty():\n",
    "            return\n",
    "        cur = self.head\n",
    "        pre = None\n",
    "        while cur.next is not self.head:\n",
    "            if cur.elem is item:\n",
    "                if cur is self.head:\n",
    "                    # 删除头节点\n",
    "                    rear = self.head\n",
    "                    while rear.next is not self.head:\n",
    "                        rear = rear.next\n",
    "                    self.head = cur.next\n",
    "                    rear.next = self.head\n",
    "                else:\n",
    "                    # 删除中间节点\n",
    "                    pre.next=cur.next\n",
    "                return\n",
    "            else:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "        # 尾节点\n",
    "        if cur.elem is item:\n",
    "            if pre is not None:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                self.head = None\n",
    "\n",
    "    # 搜索指定元素 O(n)\n",
    "    def search(self, item):\n",
    "        cur = self.head\n",
    "        # 判断是否为空\n",
    "        if self.is_empty():\n",
    "            return False\n",
    "        while cur.next is not self.head:\n",
    "            if cur.elem is item:\n",
    "                return True\n",
    "            else:\n",
    "                cur = cur.next\n",
    "        if cur.elem is item:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    \n",
    "if __name__ == \"__main__\":\n",
    "    sll = SingleLinkList()\n",
    "    \n",
    "    print(sll.is_empty()) # True\n",
    "    print(sll.length())   # 0\n",
    "    \n",
    "    sll.add(1) \n",
    "    print(sll.is_empty()) # False\n",
    "    print(sll.length())   # 1\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    sll.append(2)\n",
    "    sll.append(3)\n",
    "    sll.append(4)\n",
    "    sll.append(5)\n",
    "    sll.append(6)\n",
    "    sll.travel()  # 1 2 3 4 5 6\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    sll.add(0)\n",
    "    sll.travel() # 0 1 2 3 4 5 6\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    sll.insert(7,8)\n",
    "    sll.travel()  # 0 1 2 3 4 5 6 8\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    sll.insert(2,100)\n",
    "    sll.travel()  # 0 1 2 100 3 4 5 6 8\n",
    "    print(\"\\n\")\n",
    "    \n",
    "    print(sll.search(8))\n",
    "    print(\"\\n\") # True\n",
    "    \n",
    "    sll.remove(100)\n",
    "    sll.travel() # # 0 1 2 3 4 5 6 8\n",
    "    print(\"\\n\") # True\n",
    "    \n",
    "    sll.remove(0)\n",
    "    sll.travel() # # 1 2 3 4 5 6 8\n",
    "    print(\"\\n\") # True\n",
    "    \n",
    "    sll.remove(8)\n",
    "    sll.travel() # # 1 2 3 4 5 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
